/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the  "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id$
 */
package wx.xml.xalan.xalan.templates;

import java.util.Vector;

import wx.xml.xalan.xalan.res.XSLMessages;
import wx.xml.xalan.xalan.res.XSLTErrorResources;
import wx.xml.xalan.xml.utils.QName;
import wx.xml.xalan.xml.utils.WrappedRuntimeException;
import wx.xml.xalan.xpath.Expression;
import wx.xml.xalan.xpath.ExpressionNode;
import wx.xml.xalan.xpath.ExpressionOwner;
import wx.xml.xalan.xpath.XPath;
import wx.xml.xalan.xpath.axes.AxesWalker;
import wx.xml.xalan.xpath.axes.FilterExprIteratorSimple;
import wx.xml.xalan.xpath.axes.FilterExprWalker;
import wx.xml.xalan.xpath.axes.LocPathIterator;
import wx.xml.xalan.xpath.axes.SelfIteratorNoPredicate;
import wx.xml.xalan.xpath.axes.WalkerFactory;
import wx.xml.xalan.xpath.axes.WalkingIterator;
import wx.xml.xalan.xpath.operations.Variable;
import wx.xml.xalan.xpath.operations.VariableSafeAbsRef;

/**
 * This class eleminates redundent XPaths from a given subtree,
 * and also collects all absolute paths within the subtree.  First
 * it must be called as a visitor to the subtree, and then
 * eleminateRedundent must be called.
 */
public class RedundentExprEliminator extends XSLTVisitor {
    public static final boolean DEBUG                      = false;
    public static final boolean DIAGNOSE_NUM_PATHS_REDUCED = false;
    public static final boolean DIAGNOSE_MULTISTEPLIST     = false;
    static final   String PSUEDOVARNAMESPACE  = Constants.S_VENDORURL + "/xalan/psuedovar";
    private static int    m_uniquePseudoVarID = 1;
    Vector         m_paths;
    Vector         m_absPaths;
    boolean        m_isSameContext;
    AbsPathChecker m_absPathChecker = new AbsPathChecker();
    /**
     * So we can reuse it over and over again.
     */
    VarNameCollector m_varNameCollector = new VarNameCollector();

    /**
     * Construct a RedundentExprEliminator.
     */
    public RedundentExprEliminator() {
        m_isSameContext = true;
        m_absPaths = new Vector();
        m_paths = null;
    }

    private synchronized static int getPseudoVarID() {
        return m_uniquePseudoVarID++;
    }

    /**
     * Validate some assumptions about the new LocPathIterator and it's
     * owner and the state of the list.
     */
    private static void validateNewAddition(Vector paths, ExpressionOwner owner,
                                            LocPathIterator path)
        throws RuntimeException {
        assertion(owner.getExpression() == path, "owner.getExpression() != path!!!");
        int n = paths.size();
        // There should never be any duplicates in the list!
        for (int i = 0; i < n; i++) {
            ExpressionOwner ew = (ExpressionOwner) paths.elementAt(i);
            assertion(ew != owner, "duplicate owner on the list!!!");
            assertion(ew.getExpression() != path, "duplicate expression on the list!!!");
        }
    }

    /**
     * Simple assertion.
     */
    protected static void assertion(boolean b, String msg) {
        if (!b) {
            throw new RuntimeException(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_REDUNDENT_EXPR_ELIMINATOR, new Object[]{msg}));
            // "Programmer's assertion in RundundentExprEliminator: "+msg);
        }
    }

    /**
     * Method to be called after the all expressions within an
     * node context have been visited.  It eliminates redundent
     * expressions by creating a variable in the psuedoVarRecipient
     * for each redundent expression, and then rewriting the redundent
     * expression to be a variable reference.
     *
     * @param psuedoVarRecipient The recipient of the psuedo vars.  The
     *                           variables will be inserted as first children of the element, before
     *                           any existing variables.
     */
    public void eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient) {
        eleminateRedundent(psuedoVarRecipient, m_paths);
    }

    /**
     * Method to be called after the all global expressions within a stylesheet
     * have been collected.  It eliminates redundent
     * expressions by creating a variable in the psuedoVarRecipient
     * for each redundent expression, and then rewriting the redundent
     * expression to be a variable reference.
     */
    public void eleminateRedundentGlobals(StylesheetRoot stylesheet) {
        eleminateRedundent(stylesheet, m_absPaths);
    }

    /**
     * Method to be called after the all expressions within an
     * node context have been visited.  It eliminates redundent
     * expressions by creating a variable in the psuedoVarRecipient
     * for each redundent expression, and then rewriting the redundent
     * expression to be a variable reference.
     *
     * @param psuedoVarRecipient The owner of the subtree from where the
     *                           paths were collected.
     * @param paths              A vector of paths that hold ExpressionOwner objects,
     *                           which must yield LocationPathIterators.
     */
    protected void eleminateRedundent(ElemTemplateElement psuedoVarRecipient, Vector paths) {
        int n                        = paths.size();
        int numPathsEliminated       = 0;
        int numUniquePathsEliminated = 0;
        for (int i = 0; i < n; i++) {
            ExpressionOwner owner = (ExpressionOwner) paths.elementAt(i);
            if (null != owner) {
                int found = findAndEliminateRedundant(i + 1, i, owner, psuedoVarRecipient, paths);
                if (found > 0)
                    numUniquePathsEliminated++;
                numPathsEliminated += found;
            }
        }

        eleminateSharedPartialPaths(psuedoVarRecipient, paths);

        if (DIAGNOSE_NUM_PATHS_REDUCED)
            diagnoseNumPaths(paths, numPathsEliminated, numUniquePathsEliminated);
    }

    /**
     * Eliminate the shared partial paths in the expression list.
     *
     * @param psuedoVarRecipient The recipient of the psuedo vars.
     * @param paths              A vector of paths that hold ExpressionOwner objects,
     *                           which must yield LocationPathIterators.
     */
    protected void eleminateSharedPartialPaths(ElemTemplateElement psuedoVarRecipient, Vector paths) {
        MultistepExprHolder list = createMultistepExprList(paths);
        if (null != list) {
            if (DIAGNOSE_MULTISTEPLIST)
                list.diagnose();

            boolean isGlobal = (paths == m_absPaths);

            // Iterate over the list, starting with the most number of paths,
            // trying to find the longest matches first.
            int longestStepsCount = list.m_stepCount;
            for (int i = longestStepsCount - 1; i >= 1; i--) {
                MultistepExprHolder next = list;
                while (null != next) {
                    if (next.m_stepCount < i)
                        break;
                    list = matchAndEliminatePartialPaths(next, list, isGlobal, i, psuedoVarRecipient);
                    next = next.m_next;
                }
            }
        }
    }

    /**
     * For a given path, see if there are any partitial matches in the list,
     * and, if there are, replace those partial paths with psuedo variable refs,
     * and create the psuedo variable decl.
     *
     * @return The head of the list, which may have changed.
     */
    protected MultistepExprHolder matchAndEliminatePartialPaths(MultistepExprHolder testee,
                                                                MultistepExprHolder head,
                                                                boolean isGlobal,
                                                                int lengthToTest,
                                                                ElemTemplateElement varScope) {
        if (null == testee.m_exprOwner)
            return head;

        // Start with the longest possible match, and move down.
        WalkingIterator iter1 = (WalkingIterator) testee.m_exprOwner.getExpression();
        if (partialIsVariable(testee, lengthToTest))
            return head;
        MultistepExprHolder matchedPaths     = null;
        MultistepExprHolder matchedPathsTail = null;
        MultistepExprHolder meh              = head;
        while (null != meh) {
            if ((meh != testee) && (null != meh.m_exprOwner)) {
                WalkingIterator iter2 = (WalkingIterator) meh.m_exprOwner.getExpression();
                if (stepsEqual(iter1, iter2, lengthToTest)) {
                    if (null == matchedPaths) {
                        try {
                            matchedPaths = (MultistepExprHolder) testee.clone();
                            testee.m_exprOwner = null; // So it won't be processed again.
                        } catch (CloneNotSupportedException cnse) {
                        }
                        matchedPathsTail = matchedPaths;
                        matchedPathsTail.m_next = null;
                    }

                    try {
                        matchedPathsTail.m_next = (MultistepExprHolder) meh.clone();
                        meh.m_exprOwner = null; // So it won't be processed again.
                    } catch (CloneNotSupportedException cnse) {
                    }
                    matchedPathsTail = matchedPathsTail.m_next;
                    matchedPathsTail.m_next = null;
                }
            }
            meh = meh.m_next;
        }

        int matchCount = 0;
        if (null != matchedPaths) {
            ElemTemplateElement root       = isGlobal ? varScope : findCommonAncestor(matchedPaths);
            WalkingIterator     sharedIter = (WalkingIterator) matchedPaths.m_exprOwner.getExpression();
            WalkingIterator     newIter    = createIteratorFromSteps(sharedIter, lengthToTest);
            ElemVariable        var        = createPseudoVarDecl(root, newIter, isGlobal);
            if (DIAGNOSE_MULTISTEPLIST)
                System.err.println("Created var: " + var.getName() + (isGlobal ? "(Global)" : ""));
            while (null != matchedPaths) {
                ExpressionOwner owner = matchedPaths.m_exprOwner;
                WalkingIterator iter  = (WalkingIterator) owner.getExpression();

                if (DIAGNOSE_MULTISTEPLIST)
                    diagnoseLineNumber(iter);

                LocPathIterator newIter2 =
                    changePartToRef(var.getName(), iter, lengthToTest, isGlobal);
                owner.setExpression(newIter2);

                matchedPaths = matchedPaths.m_next;
            }
        }

        if (DIAGNOSE_MULTISTEPLIST)
            diagnoseMultistepList(matchCount, lengthToTest, isGlobal);
        return head;
    }

    /**
     * Check if results of partial reduction will just be a variable, in
     * which case, skip it.
     */
    boolean partialIsVariable(MultistepExprHolder testee, int lengthToTest) {
        if (1 == lengthToTest) {
            WalkingIterator wi = (WalkingIterator) testee.m_exprOwner.getExpression();
            if (wi.getFirstWalker() instanceof FilterExprWalker)
                return true;
        }
        return false;
    }

    /**
     * Tell what line number belongs to a given expression.
     */
    protected void diagnoseLineNumber(Expression expr) {
        ElemTemplateElement e = getElemFromExpression(expr);
        System.err.println("   " + e.getSystemId() + " Line " + e.getLineNumber());
    }

    /**
     * Given a linked list of expressions, find the common ancestor that is
     * suitable for holding a psuedo variable for shared access.
     */
    protected ElemTemplateElement findCommonAncestor(MultistepExprHolder head) {
        // Not sure this algorithm is the best, but will do for the moment.
        int numExprs = head.getLength();
        // The following could be made cheaper by pre-allocating large arrays,
        // but then we would have to assume a max number of reductions,
        // which I am not inclined to do right now.
        ElemTemplateElement[] elems          = new ElemTemplateElement[numExprs];
        int[]                 ancestorCounts = new int[numExprs];

        // Loop through, getting the parent elements, and counting the
        // ancestors.
        MultistepExprHolder next                  = head;
        int                 shortestAncestorCount = 10000;
        for (int i = 0; i < numExprs; i++) {
            ElemTemplateElement elem =
                getElemFromExpression(next.m_exprOwner.getExpression());
            elems[i] = elem;
            int numAncestors = countAncestors(elem);
            ancestorCounts[i] = numAncestors;
            if (numAncestors < shortestAncestorCount) {
                shortestAncestorCount = numAncestors;
            }
            next = next.m_next;
        }

        // Now loop through and "correct" the elements that have more ancestors.
        for (int i = 0; i < numExprs; i++) {
            if (ancestorCounts[i] > shortestAncestorCount) {
                int numStepCorrection = ancestorCounts[i] - shortestAncestorCount;
                for (int j = 0; j < numStepCorrection; j++) {
                    elems[i] = elems[i].getParentElem();
                }
            }
        }

        // Now everyone has an equal number of ancestors.  Walk up from here
        // equally until all are equal.
        ElemTemplateElement first = null;
        while (shortestAncestorCount-- >= 0) {
            boolean areEqual = true;
            first = elems[0];
            for (int i = 1; i < numExprs; i++) {
                if (first != elems[i]) {
                    areEqual = false;
                    break;
                }
            }
            // This second check is to make sure we have a common ancestor that is not the same
            // as the expression owner... i.e. the var decl has to go above the expression owner.
            if (areEqual && isNotSameAsOwner(head, first) && first.canAcceptVariables()) {
                if (DIAGNOSE_MULTISTEPLIST) {
                    System.err.print(first.getClass().getName());
                    System.err.println(" at   " + first.getSystemId() + " Line " + first.getLineNumber());
                }
                return first;
            }

            for (int i = 0; i < numExprs; i++) {
                elems[i] = elems[i].getParentElem();
            }
        }

        assertion(false, "Could not find common ancestor!!!");
        return null;
    }

    /**
     * Find out if the given ElemTemplateElement is not the same as one of
     * the ElemTemplateElement owners of the expressions.
     *
     * @param head Head of linked list of expression owners.
     * @param ete  The ElemTemplateElement that is a candidate for a psuedo
     *             variable parent.
     * @return true if the given ElemTemplateElement is not the same as one of
     * the ElemTemplateElement owners of the expressions.  This is to make sure
     * we find an ElemTemplateElement that is in a viable position to hold
     * psuedo variables that are visible to the references.
     */
    protected boolean isNotSameAsOwner(MultistepExprHolder head, ElemTemplateElement ete) {
        MultistepExprHolder next = head;
        while (null != next) {
            ElemTemplateElement elemOwner = getElemFromExpression(next.m_exprOwner.getExpression());
            if (elemOwner == ete)
                return false;
            next = next.m_next;
        }
        return true;
    }

    /**
     * Count the number of ancestors that a ElemTemplateElement has.
     *
     * @param elem An representation of an element in an XSLT stylesheet.
     * @return The number of ancestors of elem (including the element itself).
     */
    protected int countAncestors(ElemTemplateElement elem) {
        int count = 0;
        while (null != elem) {
            count++;
            elem = elem.getParentElem();
        }
        return count;
    }

    /**
     * Print out diagnostics about partial multistep evaluation.
     */
    protected void diagnoseMultistepList(
        int matchCount,
        int lengthToTest,
        boolean isGlobal) {
        if (matchCount > 0) {
            System.err.print(
                "Found multistep matches: " + matchCount + ", " + lengthToTest + " length");
            if (isGlobal)
                System.err.println(" (global)");
            else
                System.err.println();
        }
    }

    /**
     * Change a given number of steps to a single variable reference.
     *
     * @param uniquePseudoVarName The name of the variable reference.
     * @param wi                  The walking iterator that is to be changed.
     * @param numSteps            The number of steps to be changed.
     * @param isGlobal            true if this will be a global reference.
     */
    protected LocPathIterator changePartToRef(final QName uniquePseudoVarName, WalkingIterator wi,
                                              final int numSteps, final boolean isGlobal) {
        Variable var = new Variable();
        var.setQName(uniquePseudoVarName);
        var.setIsGlobal(isGlobal);
        if (isGlobal) {
            ElemTemplateElement elem = getElemFromExpression(wi);
            StylesheetRoot      root = elem.getStylesheetRoot();
            Vector              vars = root.getVariablesAndParamsComposed();
            var.setIndex(vars.size() - 1);
        }

        // Walk to the first walker after the one's we are replacing.
        AxesWalker walker = wi.getFirstWalker();
        for (int i = 0; i < numSteps; i++) {
            assertion(null != walker, "Walker should not be null!");
            walker = walker.getNextWalker();
        }

        if (null != walker) {

            FilterExprWalker few = new FilterExprWalker(wi);
            few.setInnerExpression(var);
            few.exprSetParent(wi);
            few.setNextWalker(walker);
            walker.setPrevWalker(few);
            wi.setFirstWalker(few);
            return wi;
        } else {
            FilterExprIteratorSimple feis = new FilterExprIteratorSimple(var);
            feis.exprSetParent(wi.exprGetParent());
            return feis;
        }
    }

    /**
     * Create a new WalkingIterator from the steps in another WalkingIterator.
     *
     * @param wi       The iterator from where the steps will be taken.
     * @param numSteps The number of steps from the first to copy into the new
     *                 iterator.
     * @return The new iterator.
     */
    protected WalkingIterator createIteratorFromSteps(final WalkingIterator wi, int numSteps) {
        WalkingIterator newIter = new WalkingIterator(wi.getPrefixResolver());
        try {
            AxesWalker walker = (AxesWalker) wi.getFirstWalker().clone();
            newIter.setFirstWalker(walker);
            walker.setLocPathIterator(newIter);
            for (int i = 1; i < numSteps; i++) {
                AxesWalker next = (AxesWalker) walker.getNextWalker().clone();
                walker.setNextWalker(next);
                next.setLocPathIterator(newIter);
                walker = next;
            }
            walker.setNextWalker(null);
        } catch (CloneNotSupportedException cnse) {
            throw new WrappedRuntimeException(cnse);
        }
        return newIter;
    }

    /**
     * Compare a given number of steps between two iterators, to see if they are equal.
     *
     * @param iter1    The first iterator to compare.
     * @param iter2    The second iterator to compare.
     * @param numSteps The number of steps to compare.
     * @return true If the given number of steps are equal.
     */
    protected boolean stepsEqual(WalkingIterator iter1, WalkingIterator iter2,
                                 int numSteps) {
        AxesWalker aw1 = iter1.getFirstWalker();
        AxesWalker aw2 = iter2.getFirstWalker();

        for (int i = 0; (i < numSteps); i++) {
            if ((null == aw1) || (null == aw2))
                return false;

            if (!aw1.deepEquals(aw2))
                return false;

            aw1 = aw1.getNextWalker();
            aw2 = aw2.getNextWalker();
        }

        assertion((null != aw1) || (null != aw2), "Total match is incorrect!");

        return true;
    }

    /**
     * For the reduction of location path parts, create a list of all
     * the multistep paths with more than one step, sorted by the
     * number of steps, with the most steps occuring earlier in the list.
     * If the list is only one member, don't bother returning it.
     *
     * @param paths Vector of ExpressionOwner objects, which may contain null entries.
     *              The ExpressionOwner objects must own LocPathIterator objects.
     * @return null if no multipart paths are found or the list is only of length 1,
     * otherwise the first MultistepExprHolder in a linked list of these objects.
     */
    protected MultistepExprHolder createMultistepExprList(Vector paths) {
        MultistepExprHolder first = null;
        int                 n     = paths.size();
        for (int i = 0; i < n; i++) {
            ExpressionOwner eo = (ExpressionOwner) paths.elementAt(i);
            if (null == eo)
                continue;

            // Assuming location path iterators should be OK.
            LocPathIterator lpi      = (LocPathIterator) eo.getExpression();
            int             numPaths = countSteps(lpi);
            if (numPaths > 1) {
                if (null == first)
                    first = new MultistepExprHolder(eo, numPaths, null);
                else
                    first = first.addInSortedOrder(eo, numPaths);
            }
        }

        if ((null == first) || (first.getLength() <= 1))
            return null;
        else
            return first;
    }

    /**
     * Look through the vector from start point, looking for redundant occurances.
     * When one or more are found, create a psuedo variable declaration, insert
     * it into the stylesheet, and replace the occurance with a reference to
     * the psuedo variable.  When a redundent variable is found, it's slot in
     * the vector will be replaced by null.
     *
     * @param start               The position to start looking in the vector.
     * @param firstOccuranceIndex The position of firstOccuranceOwner.
     * @param firstOccuranceOwner The owner of the expression we are looking for.
     * @param psuedoVarRecipient  Where to put the psuedo variables.
     * @return The number of expression occurances that were modified.
     */
    protected int findAndEliminateRedundant(int start, int firstOccuranceIndex,
                                            ExpressionOwner firstOccuranceOwner,
                                            ElemTemplateElement psuedoVarRecipient,
                                            Vector paths)
        throws org.w3c.dom.DOMException {
        MultistepExprHolder head          = null;
        MultistepExprHolder tail          = null;
        int                 numPathsFound = 0;
        int                 n             = paths.size();

        Expression expr1 = firstOccuranceOwner.getExpression();
        if (DEBUG)
            assertIsLocPathIterator(expr1, firstOccuranceOwner);
        boolean         isGlobal  = (paths == m_absPaths);
        LocPathIterator lpi       = (LocPathIterator) expr1;
        int             stepCount = countSteps(lpi);
        for (int j = start; j < n; j++) {
            ExpressionOwner owner2 = (ExpressionOwner) paths.elementAt(j);
            if (null != owner2) {
                Expression expr2   = owner2.getExpression();
                boolean    isEqual = expr2.deepEquals(lpi);
                if (isEqual) {
                    LocPathIterator lpi2 = (LocPathIterator) expr2;
                    if (null == head) {
                        head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
                        tail = head;
                        numPathsFound++;
                    }
                    tail.m_next = new MultistepExprHolder(owner2, stepCount, null);
                    tail = tail.m_next;

                    // Null out the occurance, so we don't have to test it again.
                    paths.setElementAt(null, j);

                    // foundFirst = true;
                    numPathsFound++;
                }
            }
        }

        // Change all globals in xsl:templates, etc, to global vars no matter what.
        if ((0 == numPathsFound) && isGlobal) {
            head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
            numPathsFound++;
        }

        if (null != head) {
            ElemTemplateElement root       = isGlobal ? psuedoVarRecipient : findCommonAncestor(head);
            LocPathIterator     sharedIter = (LocPathIterator) head.m_exprOwner.getExpression();
            ElemVariable        var        = createPseudoVarDecl(root, sharedIter, isGlobal);
            if (DIAGNOSE_MULTISTEPLIST)
                System.err.println("Created var: " + var.getName() + (isGlobal ? "(Global)" : ""));
            QName uniquePseudoVarName = var.getName();
            while (null != head) {
                ExpressionOwner owner = head.m_exprOwner;
                if (DIAGNOSE_MULTISTEPLIST)
                    diagnoseLineNumber(owner.getExpression());
                changeToVarRef(uniquePseudoVarName, owner, paths, root);
                head = head.m_next;
            }
            // Replace the first occurance with the variable's XPath, so
            // that further reduction may take place if needed.
            paths.setElementAt(var.getSelect(), firstOccuranceIndex);
        }

        return numPathsFound;
    }

    /**
     * To be removed.
     */
    protected int oldFindAndEliminateRedundant(int start, int firstOccuranceIndex,
                                               ExpressionOwner firstOccuranceOwner,
                                               ElemTemplateElement psuedoVarRecipient,
                                               Vector paths)
        throws org.w3c.dom.DOMException {
        QName      uniquePseudoVarName = null;
        boolean    foundFirst          = false;
        int        numPathsFound       = 0;
        int        n                   = paths.size();
        Expression expr1               = firstOccuranceOwner.getExpression();
        if (DEBUG)
            assertIsLocPathIterator(expr1, firstOccuranceOwner);
        boolean         isGlobal = (paths == m_absPaths);
        LocPathIterator lpi      = (LocPathIterator) expr1;
        for (int j = start; j < n; j++) {
            ExpressionOwner owner2 = (ExpressionOwner) paths.elementAt(j);
            if (null != owner2) {
                Expression expr2   = owner2.getExpression();
                boolean    isEqual = expr2.deepEquals(lpi);
                if (isEqual) {
                    LocPathIterator lpi2 = (LocPathIterator) expr2;
                    if (!foundFirst) {
                        foundFirst = true;
                        // Insert variable decl into psuedoVarRecipient
                        // We want to insert this into the first legitimate
                        // position for a variable.
                        ElemVariable var = createPseudoVarDecl(psuedoVarRecipient, lpi, isGlobal);
                        if (null == var)
                            return 0;
                        uniquePseudoVarName = var.getName();

                        changeToVarRef(uniquePseudoVarName, firstOccuranceOwner,
                            paths, psuedoVarRecipient);

                        // Replace the first occurance with the variable's XPath, so
                        // that further reduction may take place if needed.
                        paths.setElementAt(var.getSelect(), firstOccuranceIndex);
                        numPathsFound++;
                    }

                    changeToVarRef(uniquePseudoVarName, owner2, paths, psuedoVarRecipient);

                    // Null out the occurance, so we don't have to test it again.
                    paths.setElementAt(null, j);

                    // foundFirst = true;
                    numPathsFound++;
                }
            }
        }

        // Change all globals in xsl:templates, etc, to global vars no matter what.
        if ((0 == numPathsFound) && (paths == m_absPaths)) {
            ElemVariable var = createPseudoVarDecl(psuedoVarRecipient, lpi, true);
            if (null == var)
                return 0;
            uniquePseudoVarName = var.getName();
            changeToVarRef(uniquePseudoVarName, firstOccuranceOwner, paths, psuedoVarRecipient);
            paths.setElementAt(var.getSelect(), firstOccuranceIndex);
            numPathsFound++;
        }
        return numPathsFound;
    }

    /**
     * Count the steps in a given location path.
     *
     * @param lpi The location path iterator that owns the steps.
     * @return The number of steps in the given location path.
     */
    protected int countSteps(LocPathIterator lpi) {
        if (lpi instanceof WalkingIterator) {
            WalkingIterator wi    = (WalkingIterator) lpi;
            AxesWalker      aw    = wi.getFirstWalker();
            int             count = 0;
            while (null != aw) {
                count++;
                aw = aw.getNextWalker();
            }
            return count;
        } else
            return 1;
    }

    /**
     * Change the expression owned by the owner argument to a variable reference
     * of the given name.
     * <p>
     * Warning: For global vars, this function relies on the variable declaration
     * to which it refers having been added just prior to this function being called,
     * so that the reference index can be determined from the size of the global variables
     * list minus one.
     *
     * @param varName            The name of the variable which will be referenced.
     * @param owner              The owner of the expression which will be replaced by a variable ref.
     * @param paths              The paths list that the iterator came from, mainly to determine
     *                           if this is a local or global reduction.
     * @param psuedoVarRecipient The element within whose scope the variable is
     *                           being inserted, possibly a StylesheetRoot.
     */
    protected void changeToVarRef(QName varName, ExpressionOwner owner,
                                  Vector paths, ElemTemplateElement psuedoVarRecipient) {
        Variable varRef = (paths == m_absPaths) ? new VariableSafeAbsRef() : new Variable();
        varRef.setQName(varName);
        if (paths == m_absPaths) {
            StylesheetRoot root       = (StylesheetRoot) psuedoVarRecipient;
            Vector         globalVars = root.getVariablesAndParamsComposed();
            // Assume this operation is occuring just after the decl has
            // been added.
            varRef.setIndex(globalVars.size() - 1);
            varRef.setIsGlobal(true);
        }
        owner.setExpression(varRef);
    }

    /**
     * Create a psuedo variable reference that will represent the
     * shared redundent XPath, and add it to the stylesheet.
     *
     * @param psuedoVarRecipient The broadest scope of where the variable
     *                           should be inserted, usually an xsl:template or xsl:for-each.
     * @param lpi                The LocationPathIterator that the variable should represent.
     * @param isGlobal           true if the paths are global.
     * @return The new psuedo var element.
     */
    protected ElemVariable createPseudoVarDecl(
        ElemTemplateElement psuedoVarRecipient,
        LocPathIterator lpi, boolean isGlobal)
        throws org.w3c.dom.DOMException {
        QName uniquePseudoVarName = new QName(PSUEDOVARNAMESPACE, "#" + getPseudoVarID());

        if (isGlobal) {
            return createGlobalPseudoVarDecl(uniquePseudoVarName,
                (StylesheetRoot) psuedoVarRecipient, lpi);
        } else
            return createLocalPseudoVarDecl(uniquePseudoVarName, psuedoVarRecipient, lpi);
    }

    /**
     * Create a psuedo variable reference that will represent the
     * shared redundent XPath, for a local reduction.
     *
     * @param uniquePseudoVarName The name of the new variable.
     * @param stylesheetRoot      The broadest scope of where the variable
     *                            should be inserted, which must be a StylesheetRoot element in this case.
     * @param lpi                 The LocationPathIterator that the variable should represent.
     * @return null if the decl was not created, otherwise the new Pseudo var
     * element.
     */
    protected ElemVariable createGlobalPseudoVarDecl(QName uniquePseudoVarName,
                                                     StylesheetRoot stylesheetRoot,
                                                     LocPathIterator lpi)
        throws org.w3c.dom.DOMException {
        ElemVariable psuedoVar = new ElemVariable();
        psuedoVar.setIsTopLevel(true);
        XPath xpath = new XPath(lpi);
        psuedoVar.setSelect(xpath);
        psuedoVar.setName(uniquePseudoVarName);

        Vector globalVars = stylesheetRoot.getVariablesAndParamsComposed();
        psuedoVar.setIndex(globalVars.size());
        globalVars.addElement(psuedoVar);
        return psuedoVar;
    }

    /**
     * Create a psuedo variable reference that will represent the
     * shared redundent XPath, for a local reduction.
     *
     * @param uniquePseudoVarName The name of the new variable.
     * @param psuedoVarRecipient  The broadest scope of where the variable
     *                            should be inserted, usually an xsl:template or xsl:for-each.
     * @param lpi                 The LocationPathIterator that the variable should represent.
     * @return null if the decl was not created, otherwise the new Pseudo var
     * element.
     */
    protected ElemVariable createLocalPseudoVarDecl(QName uniquePseudoVarName,
                                                    ElemTemplateElement psuedoVarRecipient,
                                                    LocPathIterator lpi)
        throws org.w3c.dom.DOMException {
        ElemVariable psuedoVar = new ElemVariablePsuedo();

        XPath xpath = new XPath(lpi);
        psuedoVar.setSelect(xpath);
        psuedoVar.setName(uniquePseudoVarName);

        ElemVariable var = addVarDeclToElem(psuedoVarRecipient, lpi, psuedoVar);

        lpi.exprSetParent(var);

        return var;
    }

    /**
     * Add the given variable to the psuedoVarRecipient.
     */
    protected ElemVariable addVarDeclToElem(
        ElemTemplateElement psuedoVarRecipient,
        LocPathIterator lpi,
        ElemVariable psuedoVar)
        throws org.w3c.dom.DOMException {
        // Create psuedo variable element
        ElemTemplateElement ete = psuedoVarRecipient.getFirstChildElem();

        lpi.callVisitors(null, m_varNameCollector);

        // If the location path contains variables, we have to insert the
        // psuedo variable after the reference. (Otherwise, we want to
        // insert it as close as possible to the top, so we'll be sure
        // it is in scope for any other vars.
        if (m_varNameCollector.getVarCount() > 0) {
            ElemTemplateElement baseElem = getElemFromExpression(lpi);
            ElemVariable        varElem  = getPrevVariableElem(baseElem);
            while (null != varElem) {
                if (m_varNameCollector.doesOccur(varElem.getName())) {
                    psuedoVarRecipient = varElem.getParentElem();
                    ete = varElem.getNextSiblingElem();
                    break;
                }
                varElem = getPrevVariableElem(varElem);
            }
        }

        if ((null != ete) && (Constants.ELEMNAME_PARAMVARIABLE == ete.getXSLToken())) {
            // Can't stick something in front of a param, so abandon! (see variable13.xsl)
            if (isParam(lpi))
                return null;

            while (null != ete) {
                ete = ete.getNextSiblingElem();
                if ((null != ete) && Constants.ELEMNAME_PARAMVARIABLE != ete.getXSLToken())
                    break;
            }
        }
        psuedoVarRecipient.insertBefore(psuedoVar, ete);
        m_varNameCollector.reset();
        return psuedoVar;
    }

    /**
     * Tell if the expr param is contained within an xsl:param.
     */
    protected boolean isParam(ExpressionNode expr) {
        while (null != expr) {
            if (expr instanceof ElemTemplateElement)
                break;
            expr = expr.exprGetParent();
        }
        if (null != expr) {
            ElemTemplateElement ete = (ElemTemplateElement) expr;
            while (null != ete) {
                int type = ete.getXSLToken();
                switch (type) {
                    case Constants.ELEMNAME_PARAMVARIABLE:
                        return true;
                    case Constants.ELEMNAME_TEMPLATE:
                    case Constants.ELEMNAME_STYLESHEET:
                        return false;
                }
                ete = ete.getParentElem();
            }
        }
        return false;

    }

    /**
     * Find the previous occurance of a xsl:variable.  Stop
     * the search when a xsl:for-each, xsl:template, or xsl:stylesheet is
     * encountered.
     *
     * @param elem Should be non-null template element.
     * @return The first previous occurance of an xsl:variable or xsl:param,
     * or null if none is found.
     */
    protected ElemVariable getPrevVariableElem(ElemTemplateElement elem) {
        // This could be somewhat optimized.  since getPreviousSiblingElem is a
        // fairly expensive operation.
        while (null != (elem = getPrevElementWithinContext(elem))) {
            int type = elem.getXSLToken();

            if ((Constants.ELEMNAME_VARIABLE == type) ||
                (Constants.ELEMNAME_PARAMVARIABLE == type)) {
                return (ElemVariable) elem;
            }
        }
        return null;
    }

    /**
     * Get the previous sibling or parent of the given template, stopping at
     * xsl:for-each, xsl:template, or xsl:stylesheet.
     *
     * @param elem Should be non-null template element.
     * @return previous sibling or parent, or null if previous is xsl:for-each,
     * xsl:template, or xsl:stylesheet.
     */
    protected ElemTemplateElement getPrevElementWithinContext(ElemTemplateElement elem) {
        ElemTemplateElement prev = elem.getPreviousSiblingElem();
        if (null == prev)
            prev = elem.getParentElem();
        if (null != prev) {
            int type = prev.getXSLToken();
            if ((Constants.ELEMNAME_FOREACH == type) ||
                (Constants.ELEMNAME_TEMPLATE == type) ||
                (Constants.ELEMNAME_STYLESHEET == type)) {
                prev = null;
            }
        }
        return prev;
    }

    /**
     * From an XPath expression component, get the ElemTemplateElement
     * owner.
     *
     * @param expr Should be static expression with proper parentage.
     * @return Valid ElemTemplateElement, or throw a runtime exception
     * if it is not found.
     */
    protected ElemTemplateElement getElemFromExpression(Expression expr) {
        ExpressionNode parent = expr.exprGetParent();
        while (null != parent) {
            if (parent instanceof ElemTemplateElement)
                return (ElemTemplateElement) parent;
            parent = parent.exprGetParent();
        }
        throw new RuntimeException(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_NO_TEMPLATE_PARENT, null));
        // "Programmer's error! expr has no ElemTemplateElement parent!");
    }

    /**
     * Tell if the given LocPathIterator is relative to an absolute path, i.e.
     * in not dependent on the context.
     *
     * @return true if the LocPathIterator is not dependent on the context node.
     */
    public boolean isAbsolute(LocPathIterator path) {
        int analysis = path.getAnalysisBits();
        boolean isAbs = (WalkerFactory.isSet(analysis, WalkerFactory.BIT_ROOT) ||
            WalkerFactory.isSet(analysis, WalkerFactory.BIT_ANY_DESCENDANT_FROM_ROOT));
        if (isAbs) {
            isAbs = m_absPathChecker.checkAbsolute(path);
        }
        return isAbs;
    }

    /**
     * Visit a LocationPath.
     *
     * @param owner The owner of the expression, to which the expression can
     *              be reset if rewriting takes place.
     * @param path  The LocationPath object.
     * @return true if the sub expressions should be traversed.
     */
    public boolean visitLocationPath(ExpressionOwner owner, LocPathIterator path) {
        // Don't optimize "." or single step variable paths.
        // Both of these cases could use some further optimization by themselves.
        if (path instanceof SelfIteratorNoPredicate) {
            return true;
        } else if (path instanceof WalkingIterator) {
            WalkingIterator wi = (WalkingIterator) path;
            AxesWalker      aw = wi.getFirstWalker();
            if ((aw instanceof FilterExprWalker) && (null == aw.getNextWalker())) {
                FilterExprWalker few = (FilterExprWalker) aw;
                Expression       exp = few.getInnerExpression();
                if (exp instanceof Variable)
                    return true;
            }
        }

        if (isAbsolute(path) && (null != m_absPaths)) {
            if (DEBUG)
                validateNewAddition(m_absPaths, owner, path);
            m_absPaths.addElement(owner);
        } else if (m_isSameContext && (null != m_paths)) {
            if (DEBUG)
                validateNewAddition(m_paths, owner, path);
            m_paths.addElement(owner);
        }

        return true;
    }

    /**
     * Visit a predicate within a location path.  Note that there isn't a
     * proper unique component for predicates, and that the expression will
     * be called also for whatever type Expression is.
     *
     * @param owner The owner of the expression, to which the expression can
     *              be reset if rewriting takes place.
     * @param pred  The predicate object.
     * @return true if the sub expressions should be traversed.
     */
    public boolean visitPredicate(ExpressionOwner owner, Expression pred) {
        boolean savedIsSame = m_isSameContext;
        m_isSameContext = false;

        // Any further down, just collect the absolute paths.
        pred.callVisitors(owner, this);

        m_isSameContext = savedIsSame;

        // We've already gone down the subtree, so don't go have the caller
        // go any further.
        return false;
    }

    // ==== DIAGNOSTIC AND DEBUG FUNCTIONS ====

    /**
     * Visit an XSLT top-level instruction.
     *
     * @param elem The xsl instruction element object.
     * @return true if the sub expressions should be traversed.
     */
    public boolean visitTopLevelInstruction(ElemTemplateElement elem) {
        int type = elem.getXSLToken();
        switch (type) {
            case Constants.ELEMNAME_TEMPLATE:
                return visitInstruction(elem);
            default:
                return true;
        }
    }

    /**
     * Visit an XSLT instruction.  Any element that isn't called by one
     * of the other visit methods, will be called by this method.
     *
     * @param elem The xsl instruction element object.
     * @return true if the sub expressions should be traversed.
     */
    public boolean visitInstruction(ElemTemplateElement elem) {
        int type = elem.getXSLToken();
        switch (type) {
            case Constants.ELEMNAME_CALLTEMPLATE:
            case Constants.ELEMNAME_TEMPLATE:
            case Constants.ELEMNAME_FOREACH: {

                // Just get the select value.
                if (type == Constants.ELEMNAME_FOREACH) {
                    ElemForEach efe = (ElemForEach) elem;

                    Expression select = efe.getSelect();
                    select.callVisitors(efe, this);
                }

                Vector savedPaths = m_paths;
                m_paths = new Vector();

                // Visit children.  Call the superclass callChildVisitors, because
                // we don't want to visit the xsl:for-each select attribute, or, for
                // that matter, the xsl:template's match attribute.
                elem.callChildVisitors(this, false);
                eleminateRedundentLocals(elem);

                m_paths = savedPaths;

                // select.callVisitors(efe, this);
                return false;
            }
            case Constants.ELEMNAME_NUMBER:
            case Constants.ELEMNAME_SORT:
                // Just collect absolute paths until and unless we can fully
                // analyze these cases.
                boolean savedIsSame = m_isSameContext;
                m_isSameContext = false;
                elem.callChildVisitors(this);
                m_isSameContext = savedIsSame;
                return false;

            default:
                return true;
        }
    }

    /**
     * Print out to std err the number of paths reduced.
     */
    protected void diagnoseNumPaths(Vector paths, int numPathsEliminated,
                                    int numUniquePathsEliminated) {
        if (numPathsEliminated > 0) {
            if (paths == m_paths) {
                System.err.println("Eliminated " + numPathsEliminated + " total paths!");
                System.err.println(
                    "Consolodated " + numUniquePathsEliminated + " redundent paths!");
            } else {
                System.err.println("Eliminated " + numPathsEliminated + " total global paths!");
                System.err.println(
                    "Consolodated " + numUniquePathsEliminated + " redundent global paths!");
            }
        }
    }

    /**
     * Assert that the expression is a LocPathIterator, and, if
     * not, try to give some diagnostic info.
     */
    private final void assertIsLocPathIterator(Expression expr1, ExpressionOwner eo)
        throws RuntimeException {
        if (!(expr1 instanceof LocPathIterator)) {
            String errMsg;
            if (expr1 instanceof Variable) {
                errMsg = "Programmer's assertion: expr1 not an iterator: " +
                    ((Variable) expr1).getQName();
            } else {
                errMsg = "Programmer's assertion: expr1 not an iterator: " +
                    expr1.getClass().getName();
            }
            throw new RuntimeException(errMsg + ", " +
                eo.getClass().getName() + " " +
                expr1.exprGetParent());
        }
    }

    /**
     * Since we want to sort multistep expressions by length, use
     * a linked list with elements of type MultistepExprHolder.
     */
    class MultistepExprHolder implements Cloneable {
        final int m_stepCount;
        ExpressionOwner m_exprOwner; // Will change to null once we have processed this item.
        MultistepExprHolder m_next;

        /**
         * Create a MultistepExprHolder.
         *
         * @param exprOwner the owner of the expression we are holding.
         *                  It must hold a LocationPathIterator.
         * @param stepCount The number of steps in the location path.
         */
        MultistepExprHolder(ExpressionOwner exprOwner, int stepCount, MultistepExprHolder next) {
            m_exprOwner = exprOwner;
            assertion(null != m_exprOwner, "exprOwner can not be null!");
            m_stepCount = stepCount;
            m_next = next;
        }

        /**
         * Clone this object.
         */
        public Object clone()
            throws CloneNotSupportedException {
            return super.clone();
        }

        /**
         * Add a new MultistepExprHolder in sorted order in the list.
         *
         * @param exprOwner the owner of the expression we are holding.
         *                  It must hold a LocationPathIterator.
         * @param stepCount The number of steps in the location path.
         * @return The new head of the linked list.
         */
        MultistepExprHolder addInSortedOrder(ExpressionOwner exprOwner, int stepCount) {
            MultistepExprHolder first = this;
            MultistepExprHolder next  = this;
            MultistepExprHolder prev  = null;
            while (null != next) {
                if (stepCount >= next.m_stepCount) {
                    MultistepExprHolder newholder = new MultistepExprHolder(exprOwner, stepCount, next);
                    if (null == prev)
                        first = newholder;
                    else
                        prev.m_next = newholder;

                    return first;
                }
                prev = next;
                next = next.m_next;
            }

            prev.m_next = new MultistepExprHolder(exprOwner, stepCount, null);
            return first;
        }

        /**
         * Remove the given element from the list.  'this' should
         * be the head of the list.  If the item to be removed is not
         * found, an assertion will be made.
         *
         * @param itemToRemove The item to remove from the list.
         * @return The head of the list, which may have changed if itemToRemove
         * is the same as this element.  Null if the item to remove is the
         * only item in the list.
         */
        MultistepExprHolder unlink(MultistepExprHolder itemToRemove) {
            MultistepExprHolder first = this;
            MultistepExprHolder next  = this;
            MultistepExprHolder prev  = null;
            while (null != next) {
                if (next == itemToRemove) {
                    if (null == prev)
                        first = next.m_next;
                    else
                        prev.m_next = next.m_next;

                    next.m_next = null;

                    return first;
                }
                prev = next;
                next = next.m_next;
            }

            assertion(false, "unlink failed!!!");
            return null;
        }

        /**
         * Get the number of linked list items.
         */
        int getLength() {
            int                 count = 0;
            MultistepExprHolder next  = this;
            while (null != next) {
                count++;
                next = next.m_next;
            }
            return count;
        }

        /**
         * Print diagnostics out for the multistep list.
         */
        protected void diagnose() {
            System.err.print("Found multistep iterators: " + this.getLength() + "  ");
            MultistepExprHolder next = this;
            while (null != next) {
                System.err.print("" + next.m_stepCount);
                next = next.m_next;
                if (null != next)
                    System.err.print(", ");
            }
            System.err.println();
        }

    }

}
